# encoding: utf-8
""" 
@version: v1.0 
@author: autumner 
@license: Apache Licence  
@contact: 18322313385@163.com 
@site:  https://gitee.com/autumner/pythoncookbook.git
@software: PyCharm 
@file: radix_sort.py 
@time: 2019/7/2 10:25
"""
'''
基数排序是桶排序的一种推广，它所考虑的待排记录包含不止一个关键字。
例如对一副牌的整理，可将每张牌看作一个记录，包含两个关键字：花色、面值。一般我们可以将一个有序列是先按花色划分为四大块，每一块中又再按面值大小排序。这时“花色”就是一张牌的“最主位关键字”，而“面值”是“最次位关键字”。
基数排序有两种方法：
1.MSD （主位优先法）：从高位开始进行排序
2.LSD （次位优先法）：从低位开始进行排序
'''
# LSD Radix Sort
def radixSort(nums):
    mod = 10
    div = 1
    mostBit = len(str(max(nums)))
    # 最大数的位数决定了外循环多少次
    buckets = [[] for row in range(mod)]
    # 构造mod个空桶
    while mostBit:
        for num in nums:
            # 将数据放入对应的桶中
            buckets[num // div % mod].append(num)
        i = 0
        # nums的索引
        for bucket in buckets:
            # 将数据收集起来
            while bucket:
                nums[i] = bucket.pop(0)
                # 依次取出来
                i += 1
        div *= 10
        mostBit -= 1
    return nums

# Example use
nums = [3, 2, 15, 26, 27,36, 38, 47, 2, 19, 48, 50, 44, 4]
print(radixSort(nums))
